package com.cb2.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href='https://leetcode.cn/problems/next-greater-node-in-linked-list'>链表中的下一个更大节点(Next Greater Node In Linked List)</a>
 * <p>给定一个长度为 n 的链表 head</p>
 * <p>对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。</p>
 * <p>返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [2,1,5]
 *      输出：[5,5,0]
 *
 * 示例 2：
 *      输入：head = [2,7,4,3,5]
 *      输出：[7,0,5,5,0]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表的结点数范围是 [1, 100]</li>
 *     <li>1 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/8 16:08
 */
public class LC1019NextGreaterNodeInLinkedList_M {
    static class Solution {
        /**
         * 单调栈
         */
        public int[] nextLargerNodes(ListNode head) {
            // 计算链表的长度
            int length = 0;
            ListNode currNode = head;
            while (currNode != null) {
                length++;
                currNode = currNode.next;
            }
            currNode = head;
            int[] res = new int[length];
            // int[0]-值 int[1]-下标，从0开始
            Deque<int[]> helper = new ArrayDeque<>();
            for (int idx = 0; idx < length; idx++, currNode = currNode.next) {
                int currNodeVal = currNode.val;
                while (!helper.isEmpty() && currNodeVal > helper.peekLast()[0]) {
                    res[helper.removeLast()[1]] = currNodeVal;
                }
                helper.addLast(new int[]{currNodeVal, idx});
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.nextLargerNodes(Generator.create(1, 7, 5, 1, 9, 2, 5, 1)));
        Printer.printArrayInt(solution.nextLargerNodes(Generator.create(2, 1, 5)));
        Printer.printArrayInt(solution.nextLargerNodes(Generator.create(2, 7, 4, 3, 5)));
    }
}